1. Technical Field
The present invention relates to an apparatus for data processing in general, and in particular to a binary adder. Still more particularly, the present invention relates to a high-speed carry-lookahead binary adder.
2. Description of the Prior Art
Binary adders having a carry-lookahead are well known in the art. This type of binary adder is able to add two multiple-bit binary numbers while simultaneously computing a carry signal for each bit.
In order to compute the sum of two multiple-bit binary numbers A and B, a generate signal and a propagate signal are initially produced at each bit location. The equation for a generate signal G(i) is: G(i)=A(i)B(i), and the equation for a propagate signal P(i) is: P(i)=A(i)B(i)+A(i)B(i) or A(i)xB(i), where i denotes a bit location within the binary numbers and bit 0 is the most significant bit. These generate signals and propagate signals are then utilized to produce a carry signal for each bit. The generalized equation for a carry signal C(i) is: C(i)=G(i)+P(i) G(i+1)+P(i) P(i+1) G(i+2)+P(i) P(i+1) P(i+2) G(i+3)+. . . , etc.
Due to practical limitations such as fan-in, most carry-lookahead binary adders utilize several rows (or levels) of carry-lookahead circuits to produce carry signals while producing generate signals and propagate signals at each row. A row is commonly referred to a group or groups of circuits, the results of which are required by a subsequent row of circuits for further processing. For example, in a typical 64-bit carry-lookahead adder, groups of generate signals (G) and propagate signals (P) must first be produced in the first row for each bit. Then, a 4-bit group generate signal (G4) and a 4-bit group propagate signal (P4) are then produced at the second level for each group of four bits. The equation for a 4-bit group generate signal (G4) is: G4(i)=G(i)+P(i) G(i+1)+P(i) P(i+1) G(i+2)+P(i) P(i+1) P(i+2) G(i+3); and the equation for a 4-bit group propagate signal (P4) is: P4(i)=P(i) P(i+1) P(i+2) P(i+3).
Subsequently, a 16-bit group generate signal (G16) and a 16-bit group propagate signal (P16) are produced at the third level for each group of four 4-bit group generate signals (G4). The equation for a 16-bit group generate signal (G16) is: G16(i)=G4(i)+P4(i) G4(i+4)+P4(i) P4(i+4) G4(i+8)+P4(i) P4(i+4) P4(i+8) G4(i+12); and the equation for a 16-bit group propagate signal (P16) is: P16(i)=P4(i) P4(i+4) P4(i+8) P4(i+12).
The carry signal equations are then given as follows:
C(56)=G4(56)+P4(56) G4(60); PA0 C(52)=G4(52)+P4(52) G4(56)+P4(52) P4(56) G4(60); PA0 C(48)=G16(48)=G4(48)+P4(48) G4(52)+P4(48) P4(52) G4(56)+P4(48) P4(52) P4(56) G4(60); PA0 C(32)=G16(32)+P16(32) G16(48); PA0 C(16)=G16(16)+P16(16) G16(32)+P16(16) P16(32) G16(48); and PA0 C(0)=C.sub.OUT =G16(0)+P16(0) G16(16)+P(0) P16(16) G16(32)+P(0) P16(16) P16(32) G16(48).
As shown, a four-transistor stack is required within each carry-lookahead circuit to generate the last term of the carry equation, P.sub.i P.sub.i+1 P.sub.i+2 G.sub.i+3, and a three-transistor stack is required to generate the next-to-last term of the carry equation, P.sub.i P.sub.i+1 G.sub.i+2. Stacking transistors in this manner increases the delay and decreases the overall performance of the binary adder. Consequently, it would be desirable to provide an improved method for a binary adder to generate group propagate signals and group generate signals with minimal transistor-stacking such that the speed of the binary adder will be increased.